//迷宫生成器 —— By SummerShrimp
//http://www.summershrimp.com/2015/01/%E8%BF%B7%E5%AE%AB%E7%94%9F%E6%88%90%E7%AE%97%E6%B3%95/

#include <iostream>
#include <vector>
#include <conio.h>
#include <windows.h>
#include "unionset.h"

using namespace std;

vector<vector<int> > *map = NULL;
vector<vector<bool> > *visit = NULL;
const int LocX[4] = { 0, 1, 0, -1 };
const int LocY[4] = { 1, 0, -1, 0 };
enum Direction	{ UP, RIGHT, DOWN, LEFT };
struct Point
{
	int x, y;
};
void RandomMap(int x, int y)
{
	system("cls");
	if (map != NULL)
		delete map;
	map = new vector<vector<int> >(y*2 + 2, vector<int>(x*2 + 2, '0'));
	vector<vector<int> > &map = *::map;
	UnionSet us;
	int maxm = x*y;
	while (us.Find(1)!=us.Find(maxm))
	{
		int rx = (rand() % x)+1;
		int ry = (rand() % y)+1;
		rx = rx * 2 - 1;
		ry = ry * 2 - 1;
		int loc = rand() % 4;
		if ((ry + LocY[loc]<1 || ry + LocY[loc] > y*2-1) || (rx + LocX[loc]<1 || rx + LocX[loc] > x*2-1))
			continue;
		rx += LocX[loc];
		ry += LocY[loc];
		if (ry % 2 == 0)
		{
			int tx1 = rx / 2 + 1, tx2 = tx1;
			int ty1 = ry / 2, ty2 = ry / 2 + 1;
			if (us.Find((ty1 - 1)*x + tx1) == us.Find((ty2 - 1)*x + tx2))
				continue;
			map[ry][rx] = '1';
			map[ry - 1][rx] = '1';
			map[ry + 1][rx] = '1';

			us.Merge((ty1 - 1)*x + tx1, (ty2 - 1)*x + tx2);
		}
		else
		{
			int ty1 = (ry + 1) / 2, ty2 = ty1;
			int tx1 = rx / 2, tx2 = rx / 2 + 1;
			if (us.Find((ty1 - 1)*x + tx1) == us.Find((ty2 - 1)*x + tx2))
				continue;
			map[ry][rx] = '1';
			map[ry][rx - 1] = '1';
			map[ry][rx + 1] = '1';

			us.Merge((ty1 - 1)*x + tx1, (ty2 - 1)*x + tx2);
		}
		COORD pos = { 0, 0 };
		SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos);
		for (int j = 1; j < y*2 ; ++j)
		{
			for (int i = 1; i < x*2; ++i)
			{
				printf("%c", map[j][i]);
			}
			printf("\n");
		}
		//printf("正在点(%d,%d)\t\t\n", rx, ry);

	}
	
	FILE *fp = fopen("maze.map", "w");
	fprintf(fp,"%d %d\n", x * 2 - 1, y * 2 - 1);
	for (int j = 1; j < y*2; ++j)
	{
		for (int i = 1; i < x*2; ++i)
		{
			fprintf(fp,"%c ", map[j][i]);
		}
		fprintf(fp, "\n");
	}
	fclose(fp);
	delete ::map;
	::map = NULL;
}

int main()
{
	RandomMap(10,9);
	return 0;
}